package go_leetcode

import "math"

type NumArray struct {
	nums, sums []int
	size       int
}

func constructor(nums []int) NumArray {
	n := len(nums)
	size := int(math.Sqrt(float64(n)))
	sums := make([]int, (n+size-1)/size)
	for i, num := range nums {
		sums[i/size] += num
	}
	return NumArray{nums: nums, sums: sums, size: size}
}

func (this *NumArray) Update(index int, val int) {
	this.sums[index/this.size] += val - this.nums[index]
	this.nums[index] = val
}

func (this *NumArray) SumRange(left, right int) int {
	size := this.size
	b1, b2 := left/size, right/size
	ans := 0
	if b1 == b2 {
		for i := left; i <= right; i++ {
			ans += this.nums[i]
		}
		return ans
	}
	for i := left; i < (b1+1)*size; i++ {
		ans += this.nums[i]
	}
	for i := b1 + 1; i < b2; i++ {
		ans += this.sums[i]
	}
	for i := b2 * size; i <= right; i++ {
		ans += this.nums[i]
	}
	return ans
}
